#include <iostream>  
#include <cmath>  
using namespace std;  
  
#define maxn 20  
int n, num = 1;  
  
typedef struct node {  
    int col[maxn]; // 记录每列皇后所在的行  
    int row; // 已经放置的皇后数  
} stacktype;  
  
void display(stacktype st) {  
    printf("    第%d个解为:", num++);  
    for (int i = 1; i <= n; i++)  
        printf("(%d,%d) ", st.col[i], i);  
    printf("\n");  
}  
  
bool place(stacktype st, int k) {  
    for (int i = 1; i < k; i++) {  
        if (st.col[i] == st.col[k] || abs(st.col[i] - st.col[k]) == abs(i - k))  
            return false;  
    }  
    return true;  
}  
  
void queen(int n) {  
    stacktype st;  
    st.row = 1;  
    st.col[1] = 0; // 从第一行的第一列开始放置  
    bool find;  
    while (st.row != 0) {  
        find = false;  
        for (int j = st.col[st.row] + 1; j <= n; j++) {  
            st.col[st.row] = j;  
            if (place(st, st.row)) {  
                find = true;  
                break;  
            }  
        }  
        if (find) {  
            if (st.row == n) {  
                display(st);  
                st.row--;  
            } else {  
                st.row++;  
                st.col[st.row] = 0;  
            }  
        } else {  
            st.row--;  
            if(st.row == 0 && st.col[st.row] == n) num = 1; // reset num if no solution for current n  
        }  
    }  
    if(num == 1) printf("  此%d皇后问题无解!\n", n);  
}  
  
int main() {  
    printf("n皇后问题(n<=20)求解:n=");  
    scanf("%d", &n);  
    if (n > 20) printf("n必须小于或等于20\n");  
    else {  
        printf(" %d皇后问题的求解情况如下:\n", n);  
        queen(n);  
    }  
    return 0;  
}